class ACAutomaton:
    """AC自动机（多模式字符串匹配工具）"""

    def __init__(self):
        # 根节点：字典结构，存子节点、失败指针、当前节点对应的违规词
        # children：子节点（key=字符，value=子节点对象）
        # fail：失败指针（用于快速回溯，提升匹配效率）
        # output：当前节点对应的违规词列表（比如“高薪日结”的最后一个字节点，output存“高薪日结”）
        self.root = {"children": {}, "fail": None, "output": []}

    def add_word(self, word):
        # 第一步：把单个违规词添加到“字典树”里
        node = self.root  # 从根节点开始
        for char in word:  # 逐个字符遍历违规词（比如“高薪日结”拆成“高”“薪”“日”“结”）
            if char not in node["children"]:  # 如果当前节点没有这个字符的字节的
                # 新建一个子节点
                node["children"][char] = {"children": {}, "fail": None, "output": []}
            node = node["children"][char]  # 把当前节点指向新建的子节点
        node["output"].append(word)  # 把当前节点对应的违规词列表添加到“字典树”里

    def build_fail_links(self):
        # 第二步：构建“失败指针”（AC自动机的核心，提升匹配速度）
        from collections import deque  # 导入队列（用于广度优先遍历）
        queue = deque()  # 初始化队列

        # 根节点的所有子节点、失败指针都指向根节点
        for child in self.root["children"].values():
            child["fail"] = self.root  # 根节点的所有字节，失败指针都指向根节点
            queue.append(child)  # 把所有子节点加入队列

        # 处理队列里的其他节点
        while queue:
            current_node = queue.popleft()  # 去除队列里的第一个节点
            # 遍历的当前节点的所有字节点
            for char, child_node in current_node["children"].items():
                # 找到当前节点的失败指针
                fail_node = current_node["fail"]
                # 递归查找：如果失败指针的子节点没有当前字符，就继续向上找失败指针
                while fail_node is not None and char not in fail_node["children"]:
                    fail_node = fail_node["fail"]
                # 确定子节点的失败指针：要么指向失败指针的子节点，要么指向根节点
                child_node["fail"] = fail_node["children"][char] if (fail_node and char in fail_node["children"]) else self.root
                child_node["output"].extend(child_node["fail"]["output"])
                queue.append(child_node)  # 把当前子节点加入队列，继续处理

    def search(self, text):
        # 用构建好的AC自动机，从文本中找违规词
        node = self.root  # 从根节点开始
        results = set()  # 用set存结果(依set特性，自动去重,避免重复匹配同一个词)

        for char in text:  # 逐个字符遍历待审核文本 (比如职位标题+描述）
            # 如果当前节点没有这个字符的子节点，就通过失败指针回溯
            while node is not None and char not in node["children"]:
                node = node["fail"]
            if node is None:  # 如果回溯到根节点还没有，就重新从根节点开始
                node = self.root
                continue
            node = node["children"][char]
            if node["output"]:  # 如果当前节点有违规词，就加入结果集
                results.update(node["output"])
        return list(results)  # 把set转换为list返回(方便后续处理)
